package previous.Test_0202;

import java.util.Random;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //判断字符是否唯一


    //颜色分类
    //三指针
    //0-left:0
    //left+1-i-1:1
    //i-right-1:待处理区域
    //right-n-1:2
//    n[i]=2,swap(i,right-1)
//    i++;right--;
//    n[i]=1,i++;
//    n[i]=0,swap(i,left+1)
    public void sortColors(int[] nums) {
        int len=nums.length;
        int left=-1;
        int right=len;
        for (int i = 0; i < len; i++) {
            if(nums[i]==2){
                swap(nums,right-1,i);
                right--;
            }else if(nums[i]==1){
                i++;
            }else{
                swap(nums,i,left+1);
                i++;
                left++;
            }
        }
    }
    public void swap(int[] n,int i ,int j){
        int t=0;
        t=n[i];
        n[i]=n[j];
        n[j]=t;
    }
    //排序数组
    public int[] sortArray(int[] nums) {
       qsort(nums,0,nums.length-1);
        return nums;
    }
    public void qsort(int[] n,int l,int r){
        if(l>=r){
            return ;
        }
        Random random=new Random();
        int key=n[random.nextInt(r-l+1)+l];
        int left=l-1;
        int right=r+1;
        for (int i = 0; i < right; ) {
            if(n[i]<key){
                swap(n,left+1,i);
                left++;
                i++;
            }else if(n[i]==key){
                i++;
            }else{
                swap(n,i,right-1);
                right--;
            }
        }
        qsort(n,l,left);
        qsort(n,right,r);
    }
    //数组中第k个最大的元素
    public int findKthLargest(int[] nums, int k) {
         return seek(nums,k,0,nums.length-1);
    }
    public int seek(int[] nums,int k ,int l,int r){
        if(l==r) return nums[l];
        Random random=new Random();
        int key=nums[random.nextInt(r-l+1)+l];
        int left=l-1;
        int right=r+1;
        for (int i = l; i < right; ) {
            if(nums[i]<key){
                swap(nums,i++,++left);
            }else if(nums[i]==key){
                i++;
            }else{
                swap(nums,i,--right);
            }
        }
        int a=left-l+1;
        int b=right-left-1;
        int c=r-right+1;
        if(c>k){
           return  seek(nums,k,right,r);
        }else if(c+b>=k){
            return key;
        }else
           return seek(nums,k-c-b,l,left);
    }

}
